#include "../include/steiner.h"
#include <stdlib.h>

void primGraph (graph * in, graph * tree) {

  char    *     inTree;
  int     *     distance;
  int     *     parent;
  int           i;
  int           w;
  int           v;
  int           dist;
  int           rnd;

  inTree    = (char *) malloc(sizeof(char)*(in->TotalNodes));
  distance  = (int  *) malloc(sizeof(int)*(in->TotalNodes));
  parent    = (int  *) malloc(sizeof(int)*(in->TotalNodes));
  
  for (i=0;i<(in->TotalNodes);i++) {
    inTree[i]    =  0;
    distance[i]  = -1;
    parent[i]    = -1;
  };  

  v = 0;
  distance[v] =  0;

  while (!(inTree[v])) {

    inTree[v] = 1;

    for (i=0;i<(in->TotalNodes);i++) {
      if (in->adjacency[v][i] >= 0) {
	if (!(inTree[i])) {
	  if (distance[i] >= 0) {

	    rnd = random()/(RAND_MAX/3);
	    if (v >= 3) {
	      rnd = 0;
	    };
	    
	    if (in->adjacency[v][i] < distance[i]) {
	      if (rnd != 2) {
		distance[i] = in->adjacency[v][i];
		parent[i] = v;
	      };
	    } else {
	      if (rnd == 2) {
		distance[i] = in->adjacency[v][i];
		parent[i] = v;
	      };
	    };

	  } else {
	    distance[i] = in->adjacency[v][i];
	    parent[i] = v;
	  };
	};
      };
    };

    v = 0;
    dist = -1;
    for (i=0;i<(in->TotalNodes);i++) {
      if (!(inTree[i])) {
	if (distance[i] >= 0) {
	  if (dist >= 0) {
	    if (dist > distance[i]) {
	      dist = distance[i];
	      v = i;
	    };
	  } else {
	    dist = distance[i];
	    v = i;
	  };
	};
      };
    };
    
  };

  initializeGraph(tree,in->TotalNodes);

  for (i=0;i<(tree->TotalNodes);i++) {
    if (parent[i] >= 0) {
      (tree->adjacency)[i][parent[i]] = (in->adjacency)[i][parent[i]];
      (tree->adjacency)[parent[i]][i] = (in->adjacency)[parent[i]][i];
    };
  };

  return (void) 0;

};


int MinPrimGraph (graph * in) {

  char    *     inTree;
  int     *     distance;
  int     *     parent;
  int           i;
  int           w;
  int           v;
  int           dist;
  int           rnd;
  char          bool;
  int           total;

  inTree    = (char *) malloc(sizeof(char)*(in->TotalNodes));
  distance  = (int  *) malloc(sizeof(int)*(in->TotalNodes));
  parent    = (int  *) malloc(sizeof(int)*(in->TotalNodes));
  
  for (i=0;i<(in->TotalNodes);i++) {
    inTree[i]    =  0;
    distance[i]  = -1;
    parent[i]    = -1;
  };  

  v = 0;
  distance[v] =  0;

  total = 0;

  while (!(inTree[v])) {

    inTree[v] = 1;

    for (i=0;i<(in->TotalNodes);i++) {
      if (in->adjacency[v][i] >= 0) {
	if (!(inTree[i])) {
	  if (distance[i] >= 0) {

	    if (in->adjacency[v][i] < distance[i]) {
		distance[i] = in->adjacency[v][i];
		parent[i] = v;
	    };

	  } else {
	    distance[i] = in->adjacency[v][i];
	    parent[i] = v;
	  };
	};
      };
    };

    v = 0;
    dist = -1;
    for (i=0;i<(in->TotalNodes);i++) {
      if (!(inTree[i])) {
	if (distance[i] >= 0) {
	  if (dist >= 0) {
	    if (dist > distance[i]) {
	      dist = distance[i];
	      v = i;
	    };
	  } else {
	    dist = distance[i];
	    v = i;
	  };
	};
      };
    };

    if (dist >= 0) {
      total += dist;
    };

  };

  bool = 0;

  for (i=0;i<(in->TotalNodes);i++) {
    if (distance[i] < 0) {
      return -1;
    };
  };

  return total;

};
